package sol.leetcode;

import java.util.*;

/**
 * Top K Frequent Elements
 */
public class Issue347 {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        //统计每个数的出现次数
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums) {
            Integer cnt = map.get(num);
            map.put(num, cnt == null ? 1 : cnt + 1);
        }

        //将map按照value排序
        List<Map.Entry> list = new ArrayList<Map.Entry>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry>() {
            @Override
            public int compare(Map.Entry o1, Map.Entry o2) {
                return Integer.compare((Integer) o1.getValue(), (Integer) o2.getValue());
            }
        });
        Collections.reverse(list);

        //获取结果
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < k; ++i) {
            res.add((Integer) list.get(i).getKey());
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k=2;
        System.out.println(topKFrequent(nums, k));
    }
}
